The present invention generally relates to loss-less data compression and decompression.
Data compression systems are known in the prior art that encode a stream of digital data signals into compressed digital data signals and decode the compressed digital data signals back into the original data signals. Data compression refers to any process that converts data in a given format into an alternative format having fewer bits than the original. The objective of data compression systems is to effect a savings in the amount of storage required to hold or the amount of time required to transmit a given body of digital information. The compression ratio is defined as the ratio of the length of the encoded output data to the length of the original input data. The smaller the compression ratio, the greater will be the savings in storage or time. By decreasing the required memory for data storage or the required time for data transmission, compression results in a monetary savings. If physical devices such as magnetic disks or magnetic tape are utilized to store the data files, then a smaller space is required on the device for storing the compressed data thereby utilizing fewer disks or tapes. If telephone lines or satellite links are utilized for transmitting digital information, then lower costs result when the data is compressed before transmission. Data compression devices are particularly effective if the original data contains redundancy such as having symbols or strings of symbols appear with high frequency. A data compression device transforms an input block of data into a more concise form and thereafter translates or decompresses the concise form back into the original data in its original format.
For example, it may be desired to transmit the contents of a daily newspaper via satellite link to a remote location for printing thereat. Appropriate sensors may convert the contents of the newspaper into a data stream of serially occurring characters for transmission via the communication link. If the millions of symbols comprising the contents of the newspaper were compressed before transmission and reconstituted at the receiver, a significant amount of transmission time would be saved.
To be of practical and general utility, a digital data compression system should satisfy certain criteria. The system should provide high performance with respect to the data rates provided by and accepted by the equipment with which the data compression and decompression systems are interfacing. High performance is necessary to maintain the data rates achieved in present day disk, tape, and communication systems. Thus, the data compression and decompression systems must have data bandwidths matching the bandwidths achieved in modem devices. The performance of prior art data compression and decompression systems is typically limited by the speed of the random access memories (RAM) that are used to store statistical data and guide the compression and decompression processes. High performance for a compression device is characterized by the number of read and write operations required per input character into the compressor. The fewer the number of memory cycles, the higher the performance.
Another important criterion in the design of a data compression and decompression system is compression effectiveness. Compression effectiveness is characterized by the compression ratio of the system. The compression ratio is the ratio of data storage size in compressed form divided by the size in uncompressed form. In order for data to be compressible, the data must contain redundancy. Compression effectiveness is determined by how effectively the compression procedure matches the forms of redundancy in the input data. In typical computer stored data, e.g. arrays of integers, text or programs and the like, redundancy occurs both in the nonuniform usage of individual symbology, e.g. digits, bytes, or characters, and in frequent recurrence of symbol sequences, such as common words, blank record fields, and the like. An effective data compression system should respond to both types of redundancy.
A further criterion important in the design of data compression and decompression systems is that of adaptability. Many prior art data compression procedures require prior knowledge, or the statistics, of the data being compressed. Some prior art procedures adapt to the statistics of the data as it is received. Adaptability in the prior art processes has required an inordinate degree of complexity. An adaptive compression and decompression system may be utilized over a wide range of information types, which is typically the requirement in general purpose computer facilities. It is desirable that the compression system achieves good compression ratios without prior knowledge of the data statistics. Data compression and decompression procedures currently available are generally not adaptable and so cannot be utilized for general purpose usage.
A method and apparatus that addresses the aforementioned problems, as well as other related problems, are therefore desirable.
In various embodiments, the invention provides a method and circuit are provided for compressing and decompressing data. For compression, successive units of input data are received in first register and second registers. The contents of the registers are used to address a lookup RAM, and the data stored in the lookup RAM is used to address a dictionary RAM. If output data from the dictionary RAM does not match output data from the first and second registers, a value from a dictionary counter is stored in the lookup RAM. If output data from the dictionary RAM matches output data from the first and second registers, data read from the lookup RAM is fed back for storage in the first register. The data from the first and second registers is provided as compressed output data. For decompression, the compressed data are used to populate another dictionary RAM, which is used to reconstruct the uncompressed data.
The above summary of the present invention is not intended to describe each disclosed embodiment of the present invention. The figures and detailed description that follow provide additional example embodiments and aspects of the present invention.